class Solution466 {

    // 48/49
    public static void main(String[] args) {
        String s1 = "aaaaaaaaaaaaaaaaa", s2 = "aaaa";
        int n1 = 18, n2 = 9;
        Solution466 s = new Solution466();
        int res = s.getMaxRepetitions(s1, n1, s2, n2);
        System.out.println(res);

    }

    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int i1 = 0, i2 = 0, res = 0;
        do {
            if (s2.charAt(i2 % s2.length()) == s1.charAt(i1 % s1.length())) {
                i2++;
            }
            i1++;
            if (i1 % s1.length() == 0 && i2 % s2.length() == 0) {
                int z1 = i1 / s1.length();          // 整除
                int z2 = i2 / s2.length();   // 整除
                res += z2 * (n1 / z1) / n2;
                i1 = 0;
                n1 = n1 % z1;
                i2 = 0;
            }
        } while (n1 * s1.length() > i1);
        return res + i2 / (n2 * s2.length());
    }
}